package com.hy.backtracking3;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class FullPermutation {


    /**
     * 46.全排列
     * 力扣题目链接
     *
     * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     *
     * 示例:
     *
     * 输入: [1,2,3]
     * 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
     * 思路
     * 如果对回溯算法基础还不了解的话，我还特意录制了一期视频：带你学透回溯算法（理论篇） 可以结合题解和视频一起看，希望对大家理解回溯算法有所帮助。
     *
     * 此时我们已经学习了77.组合问题、 131.分割回文串和78.子集问题，接下来看一看排列问题。
     *
     * 相信这个排列问题就算是让你用for循环暴力把结果搜索出来，这个暴力也不是很好写。
     *
     * 所以正如我们在关于回溯算法，你该了解这些！所讲的为什么回溯法是暴力搜索，效率这么低，还要用它？
     *
     * 因为一些问题能暴力搜出来就已经很不错了！
     *
     * 我以[1,2,3]为例，抽象成树形结构如下：
     */
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> getFullPermutation(int [] num,int startIndex) {
        /*if (num.length == 0){
            return res;
        }*/
        fullPermutation(num, path);
        return res;
    }

    public void fullPermutation(int [] num, LinkedList<Integer> path){
        if (path.size() == num.length){
            res.add(new ArrayList<>(path));
        }
        for (int i = 0; i < num.length; i++) {
            // 如果path中已有，则跳过
            if (path.contains(num[i])){
                continue;
            }
            path.add(num[i]);
            // 回溯
            fullPermutation(num,path);
            path.remove(path.size() -1);
        }
    }


    public static void main(String[] args) {
        FullPermutation fullPermutation = new FullPermutation();
        int [] num = {1,2,3};
        System.out.println("res: "+fullPermutation.getFullPermutation(num,0));
    }
}
